package array;

/**
 * create by yctc
 **/

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个整数数组，判断是否存在重复元素。
 *
 * 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 *
 *
 * 示例 1:
 *
 * 输入: [1,2,3,1]
 * 输出: true
 *
 * 示例 2:
 *
 * 输入: [1,2,3,4]
 * 输出: false
 */
public class RepeatingElement {
    public static void main(String[] args) {
        int nums[] = {1, 9, 5, 6, 4, 2, 8, 3, 6, 7, 2};
        System.out.println(containsDuplicateOne(nums) + "");
        System.out.println(containsDuplicateTwo(nums) + "");
        System.out.println(containsDuplicateThree(nums) + "");
        System.out.println(containsDuplicateFour(nums) + "");
    }

    /**
     * 先对数组进行排序，然后再比较。因为排序之后如果有相同的，那么相同的值肯定是挨着的，只需要在排序之后两两比较即可
     */
    public static boolean containsDuplicateOne(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * set集合中的元素是不能有重复的，在添加的时候如果有重复的，会把之前的值给覆盖，并且返回false。遍历数组中的所有值，一个个添加到集合set中，在添加的时候如果返回false，就表示有重复的，直接返回true
     */
    public static boolean containsDuplicateTwo(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 如果有重复的，set中会覆盖，导致size减小
     */
    public static boolean containsDuplicateThree(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        return set.size() == nums.length ? false : true;
    }

    /**
     * 使用异或运算，将所有值进行异或
     * 异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
     * 因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算，当出现 0 时，返回true
     */
    public static boolean containsDuplicateFour(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if ((nums[i] ^ nums[i + 1]) == 0) {
                return true;
            }
        }
        return false;
    }
}
